CORRECTION des activités

Activité 1 : A la découverte de la récursivité

1. L'escalier

a. Construction itérative

In [ ]:
import turtle
papier = turtle.Screen()
crayon = turtle.Turtle()
crayon.pensize(5)
crayon.speed(20)
crayon.color("navy")

crayon.penup()
crayon.goto(-200, -200)
crayon.pendown()

for i in range(8):
    crayon.forward(50)
    crayon.setheading(90)
    crayon.forward(50)
    crayon.setheading(0)

# masque le crayon à la fin du tracé
crayon.hideturtle()

papier.exitonclick()

b. c. fonction récursive

In [2]:
import turtle
papier = turtle.Screen()
crayon = turtle.Turtle()
crayon.pensize(5)
crayon.speed(20)
crayon.color("navy")

def dessine_une_marche():
    crayon.forward(50)
    crayon.setheading(90)
    crayon.forward(50)
    crayon.setheading(0)

def dessine_escalier(nb_marches):
    if nb_marches == 0:
        None
    else:
        dessine_une_marche()
        dessine_escalier(nb_marches-1)

crayon.penup()
crayon.goto(-200, -200)
crayon.pendown()
dessine_escalier(8)


# masque le crayon à la fin du tracé
crayon.hideturtle()

papier.exitonclick()

2. Frise

a. Fonction motif

In [1]:
#  a. Fonction motif
import turtle

def motif():
    crayon.pendown()
    crayon.setheading(90)
    crayon.forward(100)
    crayon.setheading(0)
    crayon.forward(100)
    crayon.setheading(-90)
    crayon.forward(50)
    crayon.setheading(180)
    crayon.forward(50)
    crayon.setheading(-90)
    crayon.forward(50)
    crayon.setheading(0)
    crayon.forward(100)

b. Construction itérative

In [ ]:
# Création du "papier" et du "crayon"
crayon = turtle.Turtle()
papier = turtle.Screen()

# Taille, dimension et couleur pour le papier et le crayon
papier.bgcolor("white")
papier.setup(width=700,height=700)
crayon.pensize(15)
crayon.color("black")
crayon.speed(10)


# Tracé
crayon.penup()
crayon.goto(-300,0)
for i in range(5):
    motif()

#ligne(-300,-50,450,-50)
#ligne(-300,150,450,150)


# masque le crayon à la fin du tracé
crayon.hideturtle()

# Attends un clic pour fermer la fenêtre de dessin
papier.exitonclick()

c. définition récursive de la frise

frise(n) = motif + frise(n-1)

d. fonction récursive permettant de construire la frise

In [2]:
# Création du "papier" et du "crayon"
crayon = turtle.Turtle()
papier = turtle.Screen()

# Taille, dimension et couleur pour le papier et le crayon
papier.bgcolor("white")
papier.setup(width=700,height=700)
crayon.pensize(15)
crayon.color("black")
crayon.speed(10)


# Tracé
crayon.penup()
crayon.goto(-300,0)

def dessine_frise(n):
    if n == 0:
        None
    else:
        motif()
        dessine_frise(n-1)
    

dessine_frise(5)


# masque le crayon à la fin du tracé
crayon.hideturtle()

# Attends un clic pour fermer la fenêtre de dessin
papier.exitonclick()

Activité 2 : D'autres exemples de récursivité

1. Somme des n premiers entiers

In [4]:
def somme(n):
    s = 0
    for i in range(n):
        s += i
    return s

# pour les 5 premiers entier, ici, n = 5
somme(5)
Out[4]:
10

b. somme(n) = somme(n-1) + n

c. version recursive

In [5]:
def somme(n):
        if n == 0:
            return 0
        else:
            return n + somme(n - 1)
        
# pour les 5 premiers entiers, n = 4
somme(4)
Out[5]:
10

2. Écrire à l'envers

a. Compléter et exécuter

In [6]:
def envers(chaine):
    resultat = ""
    for caractere in chaine:
        resultat = caractere + resultat
    return resultat

envers("Maison")
Out[6]:
'nosiaM'

b. On a la définition récursive suivante : envers(chaine) = chaine[-1] + envers(chaine[:-1]) ou
envers(chaine) = envers(chaine[1:]) + chaine[0]

In [8]:
 def envers_rec(chaine):
    """
    Inverse l'ordre d'une chaîne de caractères
    paramètre:
        chaine : (str) chaîne de caractères
    retour:
        chaîne de caractères
    """
    if chaine == "":
        return ""
    else:
        return envers_rec(chaine[1:]) + chaine[0]
    
envers_rec("Maison")
Out[8]:
'nosiaM'
In [10]:
def envers_rec_bis(chaine):
    """
    Inverse l'ordre d'une chaîne de caractères
    paramètre:
        chaine : (str) chaîne de caractères
    retour:
        chaîne de caractères
    """
    if chaine == "":
        return ""
    else:
        return chaine[-1] + envers_rec_bis(chaine[:-1])
    
envers_rec_bis("Maison")
Out[10]:
'nosiaM'